Description
墨墨突然对等式很感兴趣,他正在研究 \(a_1x_1+a_2x_2+...+a_nx_n=B\)
存在非负整数解的条件,他要求你编写一个程序,给定 \(N\)、\(\{a_n\}\)、以及 \(B\) 的取值范围,求出有多少 \(B\) 可以使等式存在非负整数解。
输入的第一行包含 3 个正整数,分别表示 \(N\)、\(B_{Min}\)、\(B_{Max}\) 分别表示数列的长度、\(B\) 的下界、\(B\) 的上界。输入的第二行包含 \(N\) 个整数,即数列 \(\{a_n\}\) 的值。
Output
输出一个整数,表示有多少b可以使等式存在非负整数解。
2 5 10
3 5
Sample Output
5
HINT
对于 100% 的数据,\(N\leq
12\),\(0\leq a_i\leq
5*10^5\)$,\(1\leq B_{Min},B_{Max}\leq
10^{12}\)。
分析
我们发现这已经不是简单的数论题了!(我开始并没有发现)对于这种无限取的背包问题,可以转化为取
mod 最短路的问题。具体怎么想呢?
首先我们将 \(a\) 排序(因为这道题
\(n\)
比较小其实可以不用但是这样更优秀)考虑对于 \(a_1\),对于所有能够取到的数 \(x\),都有 \(x+a1*k\)(\(k\)
任意)一定会被取到。所以我们就可以把所有能够取到的数模 \(a_1\),发现结果属于 \(0,\dots,
a_1-1\)中的一个,那么我们就把每一个 \(0,\dots, a_1\)
看做一个集合包括所有能够取到的数模 \(a_1\) 等于该值。
那么最小路怎么解释呢?相当于每次加一个数就走了一条边,我们将所有小于
\(r\) 的数模 \(a_1\) 的最小值看做最短路,求完后遍历 \(0,\dots,a_1\) 分别求 \(r\) 和 \(l-1\) 的组合的个数(前缀和)减去即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91
| #include<iostream> #include<cstdio> #include<ctype.h> #include<algorithm> #include<cstring> #include<queue> #include<utility> #include<vector> #include<functional> using namespace std; const int maxn=5e5+5; typedef long long ll; typedef pair<ll,int> pairr;
int n,a[15]; ll L, R;
struct Edge{ int to,nxt,dis; }e[maxn*10];
int head[maxn];int ecnt;
inline void addedge(int from,int to,int dis) { e[++ecnt]=(Edge){to,head[from],dis},head[from]=ecnt; }
ll dis[maxn]; bool vis[maxn]; void dijkstra() { priority_queue <pairr,vector<pairr >,greater<pairr > >q; for(int i=0;i<a[1];i++)dis[i]=(ll)1e60; dis[0]=0; q.push(make_pair(0,0)); while(!q.empty()) { int v=q.top().second;q.pop(); if(vis[v])continue;vis[v]=1; for(int i=head[v];i!=-1;i=e[i].nxt) { int u=e[i].to; ll w=(ll)e[i].dis; if(dis[u]>dis[v]+w) { dis[u]=dis[v]+w; q.push(make_pair(dis[u],u)); } } } }
inline ll getans(ll x) { ll ans=0; for(int i=0;i<a[1];i++) if(dis[i]<=R){ ll zp=max(0ll,(x-dis[i])/a[1]); if(zp*a[1]+dis[i]<x)ans++; ans+=zp; } return ans; }
int main() { scanf("%d%lld%lld",&n,&L,&R); memset(head,-1,sizeof(head)); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); if(a[i]==0)n--,i--; } sort(a+1,a+1+n); for(int i=0;i<a[1];i++) for(int j=2;j<=n;j++) addedge(i,(a[j]+i)%a[1],a[j]); dijkstra();
ll ans=0; for (int i=0;i<a[1];i++) if (dis[i]<=R) { ll l=max(0ll,(L-dis[i])/a[1]); if (l*a[1]+dis[i]<L) l++; ll r=(R-dis[i])/a[1]; if (r*a[1]+dis[i]>R) r--; ans+=r-l+1; } printf("%lld\n",ans); return 0; }
|